"""
88. 合并两个有序数组
https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150
"""
from typing import List


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        切片
        """
        # nums1[m:] = nums2[:n]
        # nums1.sort()
        """
        双指针
        """
        # p1 , p2 = 0, 0
        # sorts = []
        # while p1 < m or p2 < n:
        #     if p1 == m:
        #         sorts.append(nums2[p2])
        #         p2 += 1
        #     elif p2 == n:
        #         sorts.append(nums1[p1])
        #         p1 += 1
        #     elif nums1[p1] <= nums2[p2]:
        #         sorts.append(nums1[p1])
        #         p1 += 1
        #     else:
        #         sorts.append(nums2[p2])
        #         p2 += 1
        # nums1[:] = sorts
        """
        逆向双指针
        """
        p1, p2 = m - 1, n - 1
        tail = m + n - 1
        while p1 >-1 or p2 > -1:
            if p1 == -1:
                nums1[tail] = nums2[p2]
                p2 -= 1
            elif p2 == -1:
                nums1[tail] = nums1[p1]
                p1 -= 1
            elif nums1[p1] >= nums2[p2]:
                nums1[tail]=nums1[p1]
                p1 -= 1
            else:
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1


if __name__ == '__main__':
    s = Solution()
    nums1 = [1, 2, 3, 0, 0, 0]
    # print(nums1[])
    nums3 = [2, 5, 6]
    m = 3
    n = 3
    s.merge(nums1, m, nums3, n)
    print(nums1)
